package com.jiang.daily.Q3219;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/31 20:57
 */
class Solution {
    // 贪心
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        int r = 1; // 表示水平有几块
        int c = 1; // 表示垂直有几块
        long expense = 0;
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        int hIndex = horizontalCut.length - 1; // 水平切索引
        int vIndex = verticalCut.length - 1; // 垂直切索引
        while(hIndex >= 0 || vIndex >= 0) {
            if (hIndex < 0 || (vIndex >= 0 && horizontalCut[hIndex] < verticalCut[vIndex])) { // 水平切全部完成 或 水平切的开销小于垂直切开销
                // 垂直切
                expense += r * verticalCut[vIndex--]; // 水平块数 * 垂直切的开销
                c++; // 垂直块数加一
            } else {
                // 水平切
                expense += c * horizontalCut[hIndex--]; // 垂直的块数 * 水平切的开销
                r++; // 水平块数加一
            }
        }
        return expense;
    }
}
